package com.ting.test.algorithms.图;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;


public class 图的拓扑遍历例题解法2 {
    public static void main(String[] args) {
        Graph graph = new Graph();
        topSort(new ArrayList<DirectedGraphNode>());
    }

    /**
     * 这里的思路是，假设节点X和节点Y，
     * 如果X的最大深度大于Y，那么X的拓扑序就在Y的前面
     * 因此，我们只需要把每个节点的深度求出，然后比较节点深度就行了
     * 注意 这里的节点深度是指的从该节点出发，所有链路中深度最大的那个
     *
     * @param directedGraphNodes
     * @return
     */
    private static List<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> directedGraphNodes) {
        if (directedGraphNodes == null || directedGraphNodes.size() == 0) {
            new ArrayList<>();
        }
        List<Record> recordList = new ArrayList<>();
        HashMap<DirectedGraphNode, Record> cache = new HashMap<>();
        for (DirectedGraphNode directedGraphNode : directedGraphNodes) {
            Record record = process(directedGraphNode, cache);
            recordList.add(record);
        }
        recordList.sort(new MyComparator());//按节点数排序
        ArrayList<DirectedGraphNode> ans = new ArrayList<DirectedGraphNode>();

        for (Record record : recordList) {
            ans.add(record.directedGraphNode);
        }
        return ans;
    }

    public static class MyComparator implements Comparator<Record> {

        @Override
        public int compare(Record o1, Record o2) {
            return o2.deep - o1.deep;
        }
    }


    /**
     * 每个节点所在子图的节点数就是他本身加上相邻的所有节点所在的节点数
     *
     * @param parent
     * @param cache  利用缓存加速
     * @return
     */
    private static Record process(DirectedGraphNode parent, HashMap<DirectedGraphNode, Record> cache) {
        //先查缓存，缓存有直接返回
        if (cache.get(parent) != null) {
            return cache.get(parent);
        }
        if (parent == null) {//base case
            return new Record(null, 0);
        }
        int deep = 0;
        for (DirectedGraphNode directedGraphNode : parent.neighbors) {
            Record record = process(directedGraphNode, cache);
            deep = Math.max(deep, record.deep);//选出相邻节点中深度最大的哪一个
        }
        // 当前节点的最大深度，就是其相邻节点的深度+1
        Record record = new Record(parent, deep + 1);
        cache.put(parent, record);//设置缓存
        return record;
    }


    // 不要提交这个类
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    public static class Record {
        DirectedGraphNode directedGraphNode;//表示当前节点
        int deep;//表示当前节点在图中的深度

        public Record(DirectedGraphNode directedGraphNode, int deep) {
            this.directedGraphNode = directedGraphNode;
            this.deep = deep;
        }
    }


}
